package problem79;

public class MySolution {
	private int[] direction1={0,1,0,-1};
	private int[] direction2={1,0,-1,0};
	
	public boolean exist(char[][] board, String word) {
		for(int i=0;i<board.length;i++){
			for(int j=0;j<board[0].length;j++){
				if(dfs(board,i,j,0,new boolean[board.length][board[0].length],word)){
					return true;
				}
			}
		}
		return false;
    }
	
	private boolean dfs(char[][] board,int i,int j,int index,boolean [][] isVisited,String word){
		if(i<0||j<0||i>=board.length||j>=board[0].length||isVisited[i][j]||board[i][j]!=word.charAt(index))
			return false;
		if(++index==word.length())return true;
		isVisited[i][j]=true;
		for(int k=0;k<4;k++){
			if(dfs(board,i+direction1[k],j+direction2[k],index,isVisited,word))	
				return true;
		}
		isVisited[i][j]=false;
		return false;
	}
}
